home *** CD-ROM | disk | FTP | other *** search
/ AI Game Programming Wisdom / AIGameProgrammingWisdom.iso / SourceCode / 11 Learning / 04 Mommersteeg / Tennis / SlidingWindow.h < prev    next >
Encoding:
C/C++ Source or Header  |  2001-09-23  |  6.3 KB  |  187 lines
  1. //----------------------------------------------------------------------------------------------
  2. // Sequential Prediction Demo: The positioning pattern
  3. // 
  4. // Author:  Fri Mommersteeg
  5. // Date:    10-09-2001
  6. // File:    SlidingWindow.h
  7. //----------------------------------------------------------------------------------------------
  8.  
  9. //----------------------------------------------------------------------------------------------
  10. //    A sliding window is a cyclic array of a fixed size (dynamically allocated).
  11. //    
  12. //    It is ideal for monitoring sequences. The window is shifted by one position 
  13. //    whenever a new element is added (i.e. each element at index i is moved to index i-1).
  14. //    This is efficiently done by overloading the index operator.
  15. //
  16. //    Note:
  17. //    With SetSize(), you set the size of the window. With GetSize(), you retrieve 
  18. //    the number of elements in the window. The window is initially empty after SetSize(),
  19. //    and no elements are shifted as long as the window is not entirely filled.
  20. //----------------------------------------------------------------------------------------------
  21.  
  22. #ifndef __SLIDINGWINDOW_H
  23. #define __SLIDINGWINDOW_H
  24.  
  25. //----------------------------------------------------------------------------------------------
  26. // Include files
  27. //----------------------------------------------------------------------------------------------
  28.  
  29. #include <assert.h>
  30.  
  31. //----------------------------------------------------------------------------------------------
  32. // CSlidingWindow: a simple but efficient sliding window
  33. //----------------------------------------------------------------------------------------------
  34.  
  35. template <class TData>
  36. class CSlidingWindow {
  37. public:
  38.     // construction & destruction methods
  39.                         CSlidingWindow();
  40.                         CSlidingWindow(int nSize);
  41.                         ~CSlidingWindow();
  42.  
  43.     // array manipulation methods
  44.     TData *                Add(TData elt);
  45.     int                    SetSize(int nSize);
  46.     int                 GetSize();
  47.     void                Clear();
  48.  
  49.     // content manipulation methods
  50.     const TData         operator[](int iIndex) const;
  51.     TData &                operator[](int iIndex);
  52.  
  53. protected:    
  54.     int                    m_nSize;
  55.     int                    m_iEnd;
  56.     int                    m_iNext;
  57.     TData *                m_pElements;
  58.     TData                m_Dropped;
  59. };
  60.  
  61. //----------------------------------------------------------------------------------------------
  62. // CSlidingWindow(): Constructor
  63. //----------------------------------------------------------------------------------------------
  64.  
  65. template <class TData>
  66. CSlidingWindow<TData>::CSlidingWindow() {    
  67.     m_pElements = NULL;
  68.     m_nSize = 0;    
  69.     m_iNext = 0;
  70.     m_iEnd = 0;
  71. }
  72.  
  73. //----------------------------------------------------------------------------------------------
  74. // CSlidingWindow(): Constructor 2
  75. //----------------------------------------------------------------------------------------------
  76.  
  77. template <class TData>
  78. CSlidingWindow<TData>::CSlidingWindow(int nSize) {    
  79.     m_pElements = new TData[nSize];
  80.     m_nSize = m_pElements == NULL ? 0 : nSize;
  81.     m_iNext = 0;
  82.     m_iEnd = 0;
  83. }
  84.  
  85. //----------------------------------------------------------------------------------------------
  86. // ~CSlidingWindow(): Destructor
  87. //----------------------------------------------------------------------------------------------
  88.  
  89. template <class TData>
  90. CSlidingWindow<TData>::~CSlidingWindow() {
  91.     Clear();
  92. }
  93.  
  94. //----------------------------------------------------------------------------------------------
  95. // Add(): Adds a new element to the window
  96. //----------------------------------------------------------------------------------------------
  97.  
  98. template <class TData>
  99. TData * CSlidingWindow<TData>::Add(TData elt) {
  100.     assert( m_nSize > 0 );
  101.  
  102.     if (m_iEnd < m_nSize) {
  103.         m_pElements[m_iNext] = elt;
  104.         m_iEnd ++;
  105.         m_iNext ++;
  106.         return NULL;
  107.     } else {
  108.         int index = m_iNext % m_nSize;
  109.         m_Dropped = m_pElements[index];
  110.         m_pElements[index] = elt;
  111.         m_iNext = index + 1;
  112.         return &m_Dropped;
  113.     }
  114. }
  115.  
  116. //----------------------------------------------------------------------------------------------
  117. // SetSize(): Sets the size of the window
  118. //----------------------------------------------------------------------------------------------
  119.  
  120. template <class TData>
  121. int CSlidingWindow<TData>::SetSize(int nSize) {
  122.     Clear();
  123.  
  124.     m_pElements = new TData[nSize];
  125.     m_nSize = m_pElements == NULL ? 0 : nSize;
  126.     m_iNext = 0;
  127.     m_iEnd = 0;
  128.  
  129.     return m_nSize;
  130. }
  131.  
  132. //----------------------------------------------------------------------------------------------
  133. // GetSize(): Returns the *actual* number of elements in the window
  134. //----------------------------------------------------------------------------------------------
  135.  
  136. template <class TData>
  137. int CSlidingWindow<TData>::GetSize() {
  138.     return m_iEnd;
  139. }
  140.  
  141. //----------------------------------------------------------------------------------------------
  142. // Clear(): Resets the window (not only removes the elements)
  143. //----------------------------------------------------------------------------------------------
  144.  
  145. template <class TData>
  146. void CSlidingWindow<TData>::Clear() {
  147.     if (m_pElements != NULL) {
  148.         delete [] m_pElements;
  149.         m_pElements = NULL;
  150.         m_nSize = 0;
  151.         m_iNext = 0;
  152.         m_iEnd = 0;
  153.     }
  154. }
  155.  
  156. //----------------------------------------------------------------------------------------------
  157. // operator[](): returns the element at the specified index in the window (constant)
  158. //----------------------------------------------------------------------------------------------
  159.  
  160. template <class TData>
  161. const TData CSlidingWindow<TData>::operator[](int iIndex) const {
  162.     assert(0 <= iIndex && iIndex < m_iEnd);
  163.  
  164.     if (m_iEnd < m_nSize) {        
  165.         return m_pElements[iIndex];
  166.     } else {
  167.         return m_pElements[(m_iNext + iIndex) % m_nSize];
  168.     }
  169. }
  170.  
  171. //----------------------------------------------------------------------------------------------
  172. // operator[](): returns the element at the specified index in the window (reference)
  173. //----------------------------------------------------------------------------------------------
  174.  
  175. template <class TData>
  176. TData & CSlidingWindow<TData>::operator[](int iIndex) {
  177.     assert(0 <= iIndex && iIndex < m_iEnd);
  178.  
  179.     if (m_iEnd < m_nSize) {
  180.         return m_pElements[iIndex];
  181.     } else {
  182.         return m_pElements[(m_iNext + iIndex) % m_nSize];
  183.     }
  184. }
  185.  
  186. //----------------------------------------------------------------------------------------------
  187. #endif // __SLIDINGWINDOW_H